<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><html xmlns="http://www.w3.org/1999/xhtml"><head><link rel="stylesheet" type="text/css" href="style.css" /><script type="text/javascript" src="highlight.js"></script></head><body><pre><span class="hs-pragma">{-# LANGUAGE CPP #-}</span><span class="hs-cpp">
#if __GLASGOW_HASKELL__
</span><span class="hs-pragma">{-# LANGUAGE MagicHash #-}</span><span class="hs-cpp">
#endif
</span><span class="hs-cpp">#if !defined(TESTING) &amp;&amp; defined(__GLASGOW_HASKELL__)
</span><span class="hs-pragma">{-# LANGUAGE Safe #-}</span><span class="hs-cpp">
#endif
</span><span class="hs-cpp">
#include &quot;containers.h&quot;
</span><span>
</span><span id="line-11"></span><span class="hs-comment">-----------------------------------------------------------------------------</span><span>
</span><span id="line-12"></span><span class="hs-comment">-- |</span><span>
</span><span id="line-13"></span><span class="hs-comment">-- Module      :  Utils.Containers.Internal.BitUtil</span><span>
</span><span id="line-14"></span><span class="hs-comment">-- Copyright   :  (c) Clark Gaebel 2012</span><span>
</span><span id="line-15"></span><span class="hs-comment">--                (c) Johan Tibel 2012</span><span>
</span><span id="line-16"></span><span class="hs-comment">-- License     :  BSD-style</span><span>
</span><span id="line-17"></span><span class="hs-comment">-- Maintainer  :  libraries@haskell.org</span><span>
</span><span id="line-18"></span><span class="hs-comment">-- Portability :  portable</span><span>
</span><span id="line-19"></span><span class="hs-comment">-----------------------------------------------------------------------------</span><span>
</span><span id="line-20"></span><span class="hs-comment">--</span><span>
</span><span id="line-21"></span><span class="hs-comment">-- = WARNING</span><span>
</span><span id="line-22"></span><span class="hs-comment">--</span><span>
</span><span id="line-23"></span><span class="hs-comment">-- This module is considered __internal__.</span><span>
</span><span id="line-24"></span><span class="hs-comment">--</span><span>
</span><span id="line-25"></span><span class="hs-comment">-- The Package Versioning Policy __does not apply__.</span><span>
</span><span id="line-26"></span><span class="hs-comment">--</span><span>
</span><span id="line-27"></span><span class="hs-comment">-- The contents of this module may change __in any way whatsoever__</span><span>
</span><span id="line-28"></span><span class="hs-comment">-- and __without any warning__ between minor versions of this package.</span><span>
</span><span id="line-29"></span><span class="hs-comment">--</span><span>
</span><span id="line-30"></span><span class="hs-comment">-- Authors importing this module are expected to track development</span><span>
</span><span id="line-31"></span><span class="hs-comment">-- closely.</span><span>
</span><span id="line-32"></span><span>
</span><span id="line-33"></span><span class="hs-keyword">module</span><span> </span><span class="hs-identifier">Utils.Containers.Internal.BitUtil</span><span>
</span><span id="line-34"></span><span>    </span><span class="hs-special">(</span><span> </span><span class="annot"><a href="Utils.Containers.Internal.BitUtil.html#bitcount"><span class="hs-identifier">bitcount</span></a></span><span>
</span><span id="line-35"></span><span>    </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Utils.Containers.Internal.BitUtil.html#highestBitMask"><span class="hs-identifier">highestBitMask</span></a></span><span>
</span><span id="line-36"></span><span>    </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Utils.Containers.Internal.BitUtil.html#shiftLL"><span class="hs-identifier">shiftLL</span></a></span><span>
</span><span id="line-37"></span><span>    </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Utils.Containers.Internal.BitUtil.html#shiftRL"><span class="hs-identifier">shiftRL</span></a></span><span>
</span><span id="line-38"></span><span>    </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Utils.Containers.Internal.BitUtil.html#wordSize"><span class="hs-identifier">wordSize</span></a></span><span>
</span><span id="line-39"></span><span>    </span><span class="hs-special">)</span><span> </span><span class="hs-keyword">where</span><span class="hs-cpp">

#if !MIN_VERSION_base(4,8,0)
</span><span class="hs-keyword">import</span><span> </span><span class="hs-identifier">Data.Bits</span><span> </span><span class="hs-special">(</span><span class="hs-special">(</span><span class="hs-operator">.|.</span><span class="hs-special">)</span><span class="hs-special">,</span><span> </span><span class="hs-identifier">xor</span><span class="hs-special">)</span><span class="hs-cpp">
#endif
</span><span class="hs-keyword">import</span><span> </span><span class="annot"><a href="../../base/src/Data.Bits.html#"><span class="hs-identifier">Data.Bits</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="../../base/src/Data.Bits.html#popCount"><span class="hs-identifier">popCount</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="../../base/src/Data.Bits.html#unsafeShiftL"><span class="hs-identifier">unsafeShiftL</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="../../base/src/Data.Bits.html#unsafeShiftR"><span class="hs-identifier">unsafeShiftR</span></a></span><span class="hs-cpp">
#if MIN_VERSION_base(4,8,0)
</span><span>    </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="../../base/src/Data.Bits.html#countLeadingZeros"><span class="hs-identifier">countLeadingZeros</span></a></span><span class="hs-cpp">
#endif
</span><span>    </span><span class="hs-special">)</span><span class="hs-cpp">
#if MIN_VERSION_base(4,7,0)
</span><span class="hs-keyword">import</span><span> </span><span class="annot"><a href="../../base/src/Data.Bits.html#"><span class="hs-identifier">Data.Bits</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="../../base/src/Data.Bits.html#finiteBitSize"><span class="hs-identifier">finiteBitSize</span></a></span><span class="hs-special">)</span><span class="hs-cpp">
#else
</span><span class="hs-keyword">import</span><span> </span><span class="hs-identifier">Data.Bits</span><span> </span><span class="hs-special">(</span><span class="hs-identifier">bitSize</span><span class="hs-special">)</span><span class="hs-cpp">
#endif
</span><span class="hs-cpp">
#if !MIN_VERSION_base (4,8,0)
</span><span class="hs-keyword">import</span><span> </span><span class="hs-identifier">Data.Word</span><span> </span><span class="hs-special">(</span><span class="hs-identifier">Word</span><span class="hs-special">)</span><span class="hs-cpp">
#endif
</span><span>
</span><span id="line-59"></span><span class="hs-comment">{----------------------------------------------------------------------
  [bitcount] as posted by David F. Place to haskell-cafe on April 11, 2006,
  based on the code on
  http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan,
  where the following source is given:
    Published in 1988, the C Programming Language 2nd Ed. (by Brian W.
    Kernighan and Dennis M. Ritchie) mentions this in exercise 2-9. On April
    19, 2006 Don Knuth pointed out to me that this method &quot;was first published
    by Peter Wegner in CACM 3 (1960), 322. (Also discovered independently by
    Derrick Lehmer and published in 1964 in a book edited by Beckenbach.)&quot;
----------------------------------------------------------------------}</span><span>
</span><span id="line-70"></span><span>
</span><span id="line-71"></span><span class="annot"><a href="Utils.Containers.Internal.BitUtil.html#bitcount"><span class="hs-identifier hs-type">bitcount</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Int</span></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Word</span></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Int</span></span><span>
</span><span id="line-72"></span><span id="bitcount"><span class="annot"><span class="annottext">bitcount :: Int -&gt; Word -&gt; Int
</span><a href="Utils.Containers.Internal.BitUtil.html#bitcount"><span class="hs-identifier hs-var hs-var">bitcount</span></a></span></span><span> </span><span id="local-6989586621679158208"><span class="annot"><span class="annottext">Int
</span><a href="#local-6989586621679158208"><span class="hs-identifier hs-var">a</span></a></span></span><span> </span><span id="local-6989586621679158207"><span class="annot"><span class="annottext">Word
</span><a href="#local-6989586621679158207"><span class="hs-identifier hs-var">x</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Int
</span><a href="#local-6989586621679158208"><span class="hs-identifier hs-var">a</span></a></span><span> </span><span class="annot"><span class="annottext">Int -&gt; Int -&gt; Int
forall a. Num a =&gt; a -&gt; a -&gt; a
</span><a href="../../base/src/GHC.Num.html#%2B"><span class="hs-operator hs-var">+</span></a></span><span> </span><span class="annot"><span class="annottext">Word -&gt; Int
forall a. Bits a =&gt; a -&gt; Int
</span><a href="../../base/src/Data.Bits.html#popCount"><span class="hs-identifier hs-var">popCount</span></a></span><span> </span><span class="annot"><span class="annottext">Word
</span><a href="#local-6989586621679158207"><span class="hs-identifier hs-var">x</span></a></span><span>
</span><span id="line-73"></span><span class="hs-pragma">{-# INLINE</span><span> </span><span class="annot"><a href="Utils.Containers.Internal.BitUtil.html#bitcount"><span class="hs-pragma hs-type">bitcount</span></a></span><span> </span><span class="hs-pragma">#-}</span><span>
</span><span id="line-74"></span><span>
</span><span id="line-75"></span><span class="hs-comment">-- The highestBitMask implementation is based on</span><span>
</span><span id="line-76"></span><span class="hs-comment">-- http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2</span><span>
</span><span id="line-77"></span><span class="hs-comment">-- which has been put in the public domain.</span><span>
</span><span id="line-78"></span><span>
</span><span id="line-79"></span><span class="hs-comment">-- | Return a word where only the highest bit is set.</span><span>
</span><span id="line-80"></span><span class="annot"><a href="Utils.Containers.Internal.BitUtil.html#highestBitMask"><span class="hs-identifier hs-type">highestBitMask</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Word</span></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Word</span></span><span class="hs-cpp">
#if MIN_VERSION_base(4,8,0)
</span><span id="highestBitMask"><span class="annot"><span class="annottext">highestBitMask :: Word -&gt; Word
</span><a href="Utils.Containers.Internal.BitUtil.html#highestBitMask"><span class="hs-identifier hs-var hs-var">highestBitMask</span></a></span></span><span> </span><span id="local-6989586621679158205"><span class="annot"><span class="annottext">Word
</span><a href="#local-6989586621679158205"><span class="hs-identifier hs-var">w</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Word -&gt; Int -&gt; Word
</span><a href="Utils.Containers.Internal.BitUtil.html#shiftLL"><span class="hs-identifier hs-var">shiftLL</span></a></span><span> </span><span class="annot"><span class="annottext">Word
</span><span class="hs-number">1</span></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Int
</span><a href="Utils.Containers.Internal.BitUtil.html#wordSize"><span class="hs-identifier hs-var">wordSize</span></a></span><span> </span><span class="annot"><span class="annottext">Int -&gt; Int -&gt; Int
forall a. Num a =&gt; a -&gt; a -&gt; a
</span><a href="../../base/src/GHC.Num.html#-"><span class="hs-glyph hs-var">-</span></a></span><span> </span><span class="annot"><span class="annottext">Int
</span><span class="hs-number">1</span></span><span> </span><span class="annot"><span class="annottext">Int -&gt; Int -&gt; Int
forall a. Num a =&gt; a -&gt; a -&gt; a
</span><a href="../../base/src/GHC.Num.html#-"><span class="hs-glyph hs-var">-</span></a></span><span> </span><span class="annot"><span class="annottext">Word -&gt; Int
forall b. FiniteBits b =&gt; b -&gt; Int
</span><a href="../../base/src/Data.Bits.html#countLeadingZeros"><span class="hs-identifier hs-var">countLeadingZeros</span></a></span><span> </span><span class="annot"><span class="annottext">Word
</span><a href="#local-6989586621679158205"><span class="hs-identifier hs-var">w</span></a></span><span class="hs-special">)</span><span class="hs-cpp">
#else
</span><span class="hs-identifier">highestBitMask</span><span> </span><span class="hs-identifier">x1</span><span> </span><span class="hs-glyph">=</span><span> </span><span class="hs-keyword">let</span><span> </span><span class="hs-identifier">x2</span><span> </span><span class="hs-glyph">=</span><span> </span><span class="hs-identifier">x1</span><span> </span><span class="hs-operator">.|.</span><span> </span><span class="hs-identifier">x1</span><span> </span><span class="hs-special">`</span><span class="hs-identifier">shiftRL</span><span class="hs-special">`</span><span> </span><span class="hs-number">1</span><span>
</span><span id="line-85"></span><span>                        </span><span class="hs-identifier">x3</span><span> </span><span class="hs-glyph">=</span><span> </span><span class="hs-identifier">x2</span><span> </span><span class="hs-operator">.|.</span><span> </span><span class="hs-identifier">x2</span><span> </span><span class="hs-special">`</span><span class="hs-identifier">shiftRL</span><span class="hs-special">`</span><span> </span><span class="hs-number">2</span><span>
</span><span id="line-86"></span><span>                        </span><span class="hs-identifier">x4</span><span> </span><span class="hs-glyph">=</span><span> </span><span class="hs-identifier">x3</span><span> </span><span class="hs-operator">.|.</span><span> </span><span class="hs-identifier">x3</span><span> </span><span class="hs-special">`</span><span class="hs-identifier">shiftRL</span><span class="hs-special">`</span><span> </span><span class="hs-number">4</span><span>
</span><span id="line-87"></span><span>                        </span><span class="hs-identifier">x5</span><span> </span><span class="hs-glyph">=</span><span> </span><span class="hs-identifier">x4</span><span> </span><span class="hs-operator">.|.</span><span> </span><span class="hs-identifier">x4</span><span> </span><span class="hs-special">`</span><span class="hs-identifier">shiftRL</span><span class="hs-special">`</span><span> </span><span class="hs-number">8</span><span>
</span><span id="line-88"></span><span>                        </span><span class="hs-identifier">x6</span><span> </span><span class="hs-glyph">=</span><span> </span><span class="hs-identifier">x5</span><span> </span><span class="hs-operator">.|.</span><span> </span><span class="hs-identifier">x5</span><span> </span><span class="hs-special">`</span><span class="hs-identifier">shiftRL</span><span class="hs-special">`</span><span> </span><span class="hs-number">16</span><span class="hs-cpp">
#if !(defined(__GLASGOW_HASKELL__) &amp;&amp; WORD_SIZE_IN_BITS==32)
</span><span>                        </span><span class="hs-identifier">x7</span><span> </span><span class="hs-glyph">=</span><span> </span><span class="hs-identifier">x6</span><span> </span><span class="hs-operator">.|.</span><span> </span><span class="hs-identifier">x6</span><span> </span><span class="hs-special">`</span><span class="hs-identifier">shiftRL</span><span class="hs-special">`</span><span> </span><span class="hs-number">32</span><span>
</span><span id="line-91"></span><span>                     </span><span class="hs-keyword">in</span><span> </span><span class="hs-identifier">x7</span><span> </span><span class="hs-special">`</span><span class="hs-identifier">xor</span><span class="hs-special">`</span><span> </span><span class="hs-special">(</span><span class="hs-identifier">x7</span><span> </span><span class="hs-special">`</span><span class="hs-identifier">shiftRL</span><span class="hs-special">`</span><span> </span><span class="hs-number">1</span><span class="hs-special">)</span><span class="hs-cpp">
#else
</span><span>                     </span><span class="hs-keyword">in</span><span> </span><span class="hs-identifier">x6</span><span> </span><span class="hs-special">`</span><span class="hs-identifier">xor</span><span class="hs-special">`</span><span> </span><span class="hs-special">(</span><span class="hs-identifier">x6</span><span> </span><span class="hs-special">`</span><span class="hs-identifier">shiftRL</span><span class="hs-special">`</span><span> </span><span class="hs-number">1</span><span class="hs-special">)</span><span class="hs-cpp">
#endif
</span><span class="hs-cpp">#endif
</span><span class="hs-pragma">{-# INLINE</span><span> </span><span class="annot"><a href="Utils.Containers.Internal.BitUtil.html#highestBitMask"><span class="hs-pragma hs-type">highestBitMask</span></a></span><span> </span><span class="hs-pragma">#-}</span><span>
</span><span id="line-97"></span><span>
</span><span id="line-98"></span><span class="hs-comment">-- Right and left logical shifts.</span><span>
</span><span id="line-99"></span><span class="annot"><a href="Utils.Containers.Internal.BitUtil.html#shiftRL"><span class="hs-identifier hs-type">shiftRL</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Utils.Containers.Internal.BitUtil.html#shiftLL"><span class="hs-identifier hs-type">shiftLL</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Word</span></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Int</span></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Word</span></span><span>
</span><span id="line-100"></span><span id="shiftRL"><span class="annot"><span class="annottext">shiftRL :: Word -&gt; Int -&gt; Word
</span><a href="Utils.Containers.Internal.BitUtil.html#shiftRL"><span class="hs-identifier hs-var hs-var">shiftRL</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Word -&gt; Int -&gt; Word
forall a. Bits a =&gt; a -&gt; Int -&gt; a
</span><a href="../../base/src/Data.Bits.html#unsafeShiftR"><span class="hs-identifier hs-var">unsafeShiftR</span></a></span><span>
</span><span id="line-101"></span><span id="shiftLL"><span class="annot"><span class="annottext">shiftLL :: Word -&gt; Int -&gt; Word
</span><a href="Utils.Containers.Internal.BitUtil.html#shiftLL"><span class="hs-identifier hs-var hs-var">shiftLL</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Word -&gt; Int -&gt; Word
forall a. Bits a =&gt; a -&gt; Int -&gt; a
</span><a href="../../base/src/Data.Bits.html#unsafeShiftL"><span class="hs-identifier hs-var">unsafeShiftL</span></a></span><span>
</span><span id="line-102"></span><span>
</span><span id="line-103"></span><span class="hs-pragma">{-# INLINE</span><span> </span><span class="annot"><a href="Utils.Containers.Internal.BitUtil.html#wordSize"><span class="hs-pragma hs-type">wordSize</span></a></span><span> </span><span class="hs-pragma">#-}</span><span>
</span><span id="line-104"></span><span class="annot"><a href="Utils.Containers.Internal.BitUtil.html#wordSize"><span class="hs-identifier hs-type">wordSize</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Int</span></span><span class="hs-cpp">
#if MIN_VERSION_base(4,7,0)
</span><span id="wordSize"><span class="annot"><span class="annottext">wordSize :: Int
</span><a href="Utils.Containers.Internal.BitUtil.html#wordSize"><span class="hs-identifier hs-var hs-var">wordSize</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Word -&gt; Int
forall b. FiniteBits b =&gt; b -&gt; Int
</span><a href="../../base/src/Data.Bits.html#finiteBitSize"><span class="hs-identifier hs-var">finiteBitSize</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Word
</span><span class="hs-number">0</span></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Word</span></span><span class="hs-special">)</span><span class="hs-cpp">
#else
</span><span class="hs-identifier">wordSize</span><span> </span><span class="hs-glyph">=</span><span> </span><span class="hs-identifier">bitSize</span><span> </span><span class="hs-special">(</span><span class="hs-number">0</span><span> </span><span class="hs-glyph">::</span><span> </span><span class="hs-identifier">Word</span><span class="hs-special">)</span><span class="hs-cpp">
#endif
</span></pre></body></html>